package ahaArithmetic;

//解救小哈（深度优先解法）
public class Dfs_2 {
    static int[][] map = new int[][]{{0,0,1,0},{0,0,0,0},{0,0,1,0},{0,1,0,0},{0,0,0,1}};
    static int[][] next = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
    static int startX = 0;
    static int startY = 0;
    static int endX = 3;
    static int endY = 2;
    static int min = 999999;

    public static void main(String[] args) {
        map[startX][startY]=0;
        dfs_2(startX,startY,0);
        System.out.println(min);
    }

    public static void dfs_2(int x,int y,int step){

        //判断越界
        if( x>4 || x<0 || y>3 || y<0){
            return;
        }
        //判断障碍
        else if(map[x][y]==1){
            return;
        }
        else if(x==endX && y==endY){
            System.out.println(step);
            if(step<min){
                min = step;
            }
            return;
        }
        map[x][y] = 1;
        //执行语句  四个方向走
        for(int i=0;i<=3;i++){
            x = x + next[i][0];
            y = y + next[i][1];
            dfs_2(x,y,step+1);
            x = x - next[i][0];
            y = y - next[i][1];
        }
        map[x][y] = 0;
    }
}
